package work.tree;

import work.TreeNode;

import java.util.HashMap;
import java.util.Map;

public class Problem437 {

    private int ans;

    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>();
        map.put(0l, 1);
        dfs(root, 0, targetSum, map);
        return ans;
    }

    private void dfs(TreeNode node, long sum, int targetSum, Map<Long, Integer> map) {
        if (node == null) {
            return;
        }
        sum += node.val;
        if (map.containsKey(sum - targetSum)) {
           ans  = ans + map.get(sum-targetSum);
        }
        map.put(sum,map.getOrDefault(sum,0)+1);
        dfs(node.left, sum, targetSum, map);
        dfs(node.right, sum, targetSum, map);
        map.put(sum,map.getOrDefault(sum,0)-1);
    }

    public static void main(String[] args) {
        Problem437 problem437 = new Problem437();
        TreeNode treeNode = new TreeNode();
        Integer[] nums = {1,-2,-3};
        TreeNode treeNode1 = treeNode.constructTree(nums);
        problem437.pathSum(treeNode1,-1);
    }
}
